#ifndef VIRTUAL_GRAPH_H_
#define VIRTUAL_GRAPH_H_

#include<unordered_set>
#include<queue>

#include "Algorithm.h"
#include "Graph.h"

class virtual_graph : public Algorithm{
    public:
        virtual_graph(){
            minDelay=kMaxValue;
        }
        ~virtual_graph();
        void SetupTopology(Graph* graph) override;
        Path FindPath(const Flow& flow) override;
        void makeVirtualGraph();

    private:
        struct virtual_link{
            NodeId source_id; //虚拟边起点
            NodeId ter_id;    //虚拟边终点
            int cost;         //总损耗
            int delay;        //总延迟
            std::vector<int> C_units;
            std::vector<int> nodes_passed;
            std::unordered_set<int> nodes_passed_set;
            virtual_link(){}
            virtual_link(NodeId source, NodeId ter):source_id(source),ter_id(ter){
                cost = 0;
                delay = 0;
            }
            virtual_link(virtual_link *lk){
                source_id=lk->source_id;
                ter_id=lk->ter_id;
                cost=lk->cost;
                delay=lk->delay;
                nodes_passed=lk->nodes_passed;
                nodes_passed_set=lk->nodes_passed_set;
            }
        };


        std::vector<std::vector<virtual_link *>> virtual_adjList;
        int num_nodes_;
        //最终结果
        int minDelay;
        std::priority_queue<Path,std::vector<Path>,std::greater<Path>> pathList;  //小顶堆优先级队列，储存所有路线
        

    private:
        void pulse_virLink(NodeId start);
        Path pulse_findPath(NodeId from, NodeId to);
        void Dfs_virLink(int i, virtual_link *lk);
        void Dfs(NodeId end,virtual_link *edge, Path p);
        bool judge(virtual_link *edge, Path p);
        std::vector<int> intersection(std::vector<int> v1,std::vector<int> v2);
};




#endif